package leetcode.code1170;

import java.util.Arrays;

public class Solution {
	public int[] numSmallerByFrequency(String[] queries, String[] words) {
		int len = words.length;
		int[] cnts = new int[len];
		for (int i = 0; i < len; i++) {
			cnts[i] = this.f(words[i].toCharArray());
		}
		Arrays.sort(cnts);
		int[] ans = new int[queries.length];
		for (int i = 0; i < ans.length; i++) {
			int find = this.f(queries[i].toCharArray());
			int l = 0, r = len - 1;
			int index = len;
			while (l <= r) {
				int mid = l + ((r - l) >> 1);
				if (cnts[mid] > find) {
					index = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			ans[i] = len - index;
		}
		return ans;
	}

	private int f(char[] cs) {
		int ans = 0, c = 128;
		for (int i = 0; i < cs.length; i++) {
			char cur = cs[i];
			if (cur == c) {
				ans++;
			} else if (cur < c) {
				c = cur;
				ans = 1;
			}
		}
		return ans;
	}
}
